package cn.edu.anan.datastructure.line;

/**
 * 双向链表实现思路：
 *      1.空闲一个头节点，即头节点不存储数据
 *      2.这样有利于简化链表的实现
 */
public class DoubleLinkedList<E> {
    // 链表大小
    private int size;
    public int getSize() {
        return size;
    }

    // 头节点
    private Node<E> head;
    // 尾节点
    private Node<E> tail;

    public DoubleLinkedList(){
        head = new Node<E>();
        tail = head;

        size ++;
    }

    /**
     * 添加元素到链表结尾
     */
    public boolean add(E e){

        // 创建节点
        Node<E> node = new Node<E>();
        node.setE(e);
        node.setPrev(tail);

        tail.next = node;
        tail = node;

        size ++;
        return true;
    }

    /**
     * 在指定位置插入链表元素
     */
    public boolean insertPos(int pos,E e){

        // 获取位置节点
        Node<E> posNode = get(pos);
        if(posNode == null){
            return false;
        }

        // 创建新节点
        Node<E> newNode = new Node<E>();
        newNode.setE(e);
        newNode.setPrev(posNode.prev);
        newNode.setNext(posNode);

        posNode.prev.setNext(newNode);
        posNode.setPrev(newNode);

        size ++;
        return true;
    }

    /**
     * 删除链表结尾元素
     */
    public boolean remove(){

        tail = tail.prev;
        tail.next = null;

        size --;
        return false;
    }

    /**
     * 在指定位置删除链表元素
     */
    public boolean delPos(int pos){

        // 获取指定位置节点
        Node<E> node = get(pos);
        if(node == null){
            return false;
        }

        // 删除
        node.prev.setNext(node.next);
        node.next.setPrev(node.prev);

        size --;
        return true;
    }

    /**
     * 获取节点
     */
    public Node<E> get(int pos){
        // 判断位置有效性
        if(pos < 1 || pos > size){
            return null;
        }

        Node<E> node = head;
        for(int i = 1; i <= pos; i++){
            node = node.next;
        }

        return node;
    }

    /**
     * 获取节点数据
     */
    public E getValue(int pos){
        // 获取节点
        Node<E> node = get(pos);
        if(node == null){
            return null;
        }else{
            return node.e;
        }
    }

    /**
     * 节点：Node<E>
     */
    class Node<E> {
        protected E e;
        protected Node<E> prev;
        protected Node<E> next;

        public E getE() {
            return e;
        }

        public void setE(E e) {
            this.e = e;
        }

        public Node<E> getPrev() {
            return prev;
        }

        public void setPrev(Node<E> prev) {
            this.prev = prev;
        }

        public Node<E> getNext() {
            return next;
        }

        public void setNext(Node<E> next) {
            this.next = next;
        }
    }

}


